package com.zjsru.plan2024.oneday;

import java.util.HashSet;
import java.util.Set;

/**
 * 2684. 矩阵中移动的最大次数
 * 从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
 * @Author: cookLee
 * @Date: 2024-03-16
 */
public class MaxMoves {

    /**
     * 主
     * \
     * 输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
     * 输出：3
     * 解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
     * - (0, 0) -> (0, 1).
     * - (0, 1) -> (1, 2).
     * - (1, 2) -> (2, 3).
     * 可以证明这是能够移动的最大次数。
     * \
     * 输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
     * 输出：0
     * 解释：从第一列的任一单元格开始都无法移动。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MaxMoves maxMoves = new MaxMoves();
        int[][] grid = new int[][]{{2,4,3,5},{5,4,9,3},{3,4,2,11},{10,9,13,15}};
        System.out.println(maxMoves.maxMoves(grid));
    }

    /**
     * 最大移动数 bfs
     *
     * @param grid 网格
     * @return int
     */
    public int maxMoves(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        //用于存储当前可以移动到相邻元素的行数。
        Set<Integer> rowIndex = new HashSet<>();
        for (int i = 0; i < row; i++) {
            rowIndex.add(i);
        }
        for (int i = 1; i < col; i++) {
            //存储下一步可以移动到的行数
            Set<Integer> colIndex = new HashSet<>();
            //遍历当前可以移动到的行数
            for (Integer index : rowIndex) {
                //对于每一行，检查其相邻的三个位置
                for (int index2 = index - 1; index2 <= index + 1; index2++) {
                    if(0 <= index2 && index2 < row && grid[index][i - 1] < grid[index2][i]){
                        colIndex.add(index2);
                    }
                }
            }
            //更新下一步可以移动到的行数
            rowIndex = colIndex;
            if(rowIndex.isEmpty()){
                //说明已经没有可以移动到的位置
                return i - 1;
            }
        }
        //最后一列还有可以移动
        return col - 1;
    }

}
